import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> hash = new HashMap<>();
        for (String s : words) {
            hash.put(s, hash.getOrDefault(s, 0) + 1);
        }
        Set<Map.Entry<String, Integer>> entries = hash.entrySet();
        // 小根堆
        PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>(
                (a, b) -> {
                    if (a.getValue().equals(b.getValue())) {
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue() - b.getValue();
                }
        );
        for (Map.Entry<String, Integer> m : entries) {
            heap.offer(m);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while (!heap.isEmpty()) {
            Map.Entry<String, Integer> entry = heap.poll();
            ret.add(entry.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}